//找出数组中重复的数字。 
//
// 
//在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请
//找出数组中任意一个重复的数字。 
//
// 示例 1： 
//
// 输入：
//[2, 3, 1, 0, 2, 5, 3]
//输出：2 或 3 
// 
//
// 
//
// 限制： 
//
// 2 <= n <= 100000 
// Related Topics 数组 哈希表 排序 👍 682 👎 0

package com.cute.leetcode.editor.cn;
public class ShuZuZhongZhongFuDeShuZiLcof {
    public static void main(String[] args) {
        Solution solution = new ShuZuZhongZhongFuDeShuZiLcof().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 空间复杂度为n换来的时间复杂度为n
         */
        public int findRepeatNumber1(int[] nums) {
            //这样时间空间复杂度都是n
            int[] count = new int[nums.length];
            for (int num : nums){
                if (count[num] == 1) return num;
                count[num] = 1;
            }
            return -1;
        }

        /**
         * 时间复杂度为N空间为1的方法
         * 如果没有重复元素的话，对应下标i处保存的值num应该就是i
         * 遍历数组，如果当前num不等于i的话，就将其交换到应有的位置去，反复比较
         * 如果目的地位置的num已经正确了，那么当前值就是重复值
         */
        public int findRepeatNumber(int[] nums) {
            int num;
            int temp;
            for (int i = 0; i < nums.length; i++) {
                while (nums[i] != i){
                    num = nums[i];
                    if (nums[num] == num) return num;
                    temp = nums[num];
                    nums[num] = num;
                    nums[i] = temp;
                }
            }
            return -1;
        }

        /**
         * 另一个要求：不改变数组，数组长度为n+1，包含元素在1~n之间，要求空间复杂度为1
         * 如果没有重复元素的数组，比如在1 2 3中，1 2 3 出现的次数和不会 > 3（根据元素范围求得）
         * 所以可以使用二分法的思想，将数组以mid进行分割，对数组进行检索，统计在一定范围内元素出现的总次数
         * 根据count对元素重复范围进行更新
         * 二分查找时间复杂度为logn, 统计次数为n, 所以整体时间复杂度为nlogn, 空间复杂度为1
         */
        public int findRepeatNumber3(int[] nums) {
            int start = 1;
            int end = nums.length - 1;
            int mid;
            while (start <= end){
                mid = (end - start)>>1 + start;
                int count = count(nums, start, end);
                if (start == end){
                    if (count > 1) return start;
                    else break;
                }
                if (count > mid - start + 1) end = mid;
                else start = mid + 1;
            }
            return -1;
        }

        private int count(int[] nums, int start, int end) {
            int count = 0;
            for (int num : nums){
                if (num >= start && num <= end) count++;
            }
            return count;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}